package org.example.myleet.p1122;

import java.util.*;

/**
 * 简单题目
 */
public class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int len1 = arr1.length, len2 = arr2.length;
        //先求出arr2中各数字的相对位置，用于后面排序用
        Map<Integer, Integer> charPosMap = new HashMap<>(arr2.length);
        for (int i=0; i<len2; i++) {
            charPosMap.put(arr2[i], i);
        }
        Set<Integer> existChars = charPosMap.keySet();
        //将arr1拆成两部分，一部分是arr2中存在的数字，一部分是arr2中不存在的数字，分别排序
        List<Integer> arr1ExistChars = new ArrayList<>();
        List<Integer> arr1NonExistChars = new ArrayList<>();
        for (int value : arr1) {
            if (existChars.contains(value)) {
                arr1ExistChars.add(value);
            } else {
                arr1NonExistChars.add(value);
            }
        }
        //存在的数字按照相对顺序排序
        arr1ExistChars.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                Integer pos1 = charPosMap.get(o1);
                Integer pos2 = charPosMap.get(o2);
                return pos1 - pos2;
            }
        });
        //不存在的数字按照升序排序
        arr1NonExistChars.sort(Comparator.naturalOrder());
        //最终将两部分结果连接起来
        int[] result = new int[len1];
        int j=0;
        for (int i=0; i<arr1ExistChars.size(); i++) {
            result[i] = arr1ExistChars.get(i);
            ++j;
        }
        for (int i=0; i<arr1NonExistChars.size(); i++) {
            result[j] = arr1NonExistChars.get(i);
            ++j;
        }
        return result;
    }
}
